|
|
|
When CCITT found that the N-ISDN was not going to solve the actual communication problems, it tried to think of a new service. The result was broadband ISDN (B-ISDN), basically a digital virtual circuit for moving fixed-sized packets (cells) at 155 Mbps.
Broadband ISDN is based on ATM technology that is fundamentally a
packet-switching technology.
2.6.1. Virtual Circuits versus Circuit Switching
The basic broadband ISDN service is a compromise between pure circuit switching and pure packet switching. The actual service offered is connection oriented, but it is implemented internally with packet switching. Two kinds of connections are offered:
The advantage of permanent over a switched virtual circuit is that there is no setup time, packets along permanent circuit can move instantly. For some applications, such as credit card verification, saving a few seconds on each transaction may be worth the cost of the permanent circuit.
In a virtual circuit network, like ATM, when a circuit is established, what really happens is that route is chosen from source to destination, and all the switches (i.e., routers) along the way make table entries so that they can route any packet on that virtual circuit (Fig. 2-43). When a packet comes along, the switch inspects the packet header to find out which virtual circuit it belongs to. Then it looks up that virtual circuit in its tables to determine which communication line to send on.
Fig. 2-43. The dotted line shows a virtual circuit. It is simply
defined by table entries inside the switches.
ATM stands for Asynchronous Transfer Mode. This mode can be contrasted with the synchronous T1 carrier (Fig. 2-44).
Fig. 2-44 (a) Synchronous transmission mode. (b) Asynchronous
transmission mode.
T1: frames are generated precisely every 125(sec. This rate is governed by a master clock. Slot k of each frame contains 1 byte of data from the same source.
ATM: has no requirements that cells rigidly alternate among the various sources. Cells arrive randomly from different sources. The stream of cells need not be continuous. Gaps between the data are filled by special idle cells.
ATM does not standardize the format for transmitting cells. Cells are allowed to be sent individually, or they can be encased in a carrier such as T1, T3, SONET, or FDDI. For these examples, standards exist telling how cells are packed into the frames these systems provides.
In the original ATM standard, the primary rate was 155.52 Mbps, with an additional rate at four time that speed (622.08 Mbps). These rates were chosen to be compatible with SONET. ATM over T3 (44.736 Mbps) and FDDI (100 Mbps) is also foreseen.
The transmission medium for ATM is normally fiber optics, but for runs
under 100 m, coax or category 5 twisted pair are also acceptable. Each
link goes between a computer and an ATM switch, or between two ATM
switches. So, all ATM links are point-to-point. Each link is
unidirectional. For full-duplex operation, two parallel links are needed.
2.6.3. ATM Switches
An ATM cell switch (Fig. 2-45) has some number of input lines and some number of output lines (the both numbers are usually the same). ATM switches are generally synchronous in the sense of during a cycle, one cell is taken from each input line, passed into the internal switching fabric, and eventually transmitted on the appropriate output line.
Fig. 2-45. A generic ATM switch.
Switches may be pipelined, that is, it may take several cycles before an incoming cell appears on its output line. Cells actually arrive on the input lines asynchronously, so there is a master clock that marks the beginning of a cycle. Any cell fully arrived when the clock ticks is eligible for switching during that cycle. A cell not fully arrived has to wait until the next cycle.
Cells arrive at ATM speed, normally about 150 Mbps. This works out around 360000 cells/sec, the cycle time has to be about 2.7 (sec. A commercial switch might have from 16 to 1024 input lines. At 622 Mbps the cycle time has to be about 700 nsec. The fact that the cells are fixed length and short makes it possible to build such switches. With longer variable-length packets, high speed switching would be more complex, which is why ATM uses short fixed-length cells.
All ATM switches have two common goals:
A problem is if the cells arriving at more input lines want to go to the same output port in the same cycle.
One solution is to provide a queue for each input line. If more cells conflict, one of them is chosen for delivery, and the rest are held for the next cycle (Fig. 2-46). The problem with input queuing is that when a cell has to be held up, it blocks the progress of all cells behind it, even if they could otherwise be switched (head-of-line blocking).
Fig. 2-46. Input queueing at an ATM switch.
An alternative design, one that does not exhibit head-of-line blocking, does the queuing on the output side (Fig. 2-47). In our example, it takes only three cycles, instead of four in the previous example, to switch all packets. Output queuing is generally more efficient than input queuing.
Fig. 2-47. Output queueing at an ATM switch.
In Fig. 2-48, there is one ATM switch design, that uses output queuing, called knockout switch. Each input line is connected to a bus on which incoming cells are broadcasted in the cycle they arrive.
Fig. 2-48. A simplified diagram of the knockout switch.
For each arriving cell, hardware inspects the cell's header to find its virtual circuit information, looks up in the routing tables, and enables the correct crosspoint through which it gets to its output line. In case multiple cells want to go to the same output line a problem arises. The simplest way to solve such a problem is to buffer all cells at the output side. For switches with many inputs (say 1024) it is not reasonable to have a buffer for each output. In practice, reasonable optimization is to provide fewer output buffers, say n.
If more than n cells arrive in one cycle, the concentrator on each line selects out n cells for queuing, discarding the rest. It makes this selection using an elimination (knockout) tournament.
Conceptually, all the selected cells go into a single output queue
(unless it is full, in which case cells are discarded). Because of timing
reasons, the output queue is simulated by multiple queues. The selected
cells go into a shifter, which then distributes them uniformly over n
output queues using a token to keep track of which queue goes next,
in order to maintain sequencing within each virtual circuit.
2.6.5. The Batcher-Banyan Switch
The problem with the knockout switch is that the number of crosspoints is quadratic in the number of lines. As with the crossbar switches for circuit switching, the solution is the space division switching requiring a multistage switch. This solution is called the Batcher-banyan switch.
In banyan switches, only one path exists from each input line to each output line (see Fig. 2-49(a) for 8 x 8 three-stage banyan switch). Routing is done by looking up the output line for each cell (based on virtual circuit information and tables). This 3 bit binary number is then put in front of the cell, as it will be used for routing through the switch.
Fig. 2-49. (a) A banyan switch with eight input lines and
eight output lines.
(b) The routes that two cells take
through the banyan switch.
Each of the 12 switching elements in the banyan switch has two inputs and 2 outputs. When a cell arrives at a switching element, 1 bit of the output line number is inspected, and based on that, the cell is routed either to port 0 (the upper one) or port 1 (the lower one). In the event of collision, one cell is routed and one is discarded.
A banyan switch parses the output line number from left to right (see Fig. 2-49(b) for an example).
Examples in Fig. 2-50 show that depending on input, the banyan switch can do a good job or a bad job of routing.
Fig. 2-50. (a) Cells colliding in a banyan switch. (b)
Collision-free routing through a banyan switch.
The idea behind the Batcher-banyan switch is to put a switch in front of the banyan switch to permute the cells into a configuration that the banyan switch can handle without loss. For example, if the incoming cells are sorted by destination and presented on input lines 0, 2, 4, 6, 1, 3, 5, and 7, in that order as far as necessary (depending of how many cells there are), then the banyan switch does not lose cells.
To sort the incoming cells we can use a Batcher switch built up of 2 x 2 switching elements. When such a switching element receives two cells, it compares their output addresses numerically (thus no just 1 bit) and routes the higher one on the port in the direction of arrow, and the lower one on the other way. If there is only one cell, it goes to the port opposite the way the arrow is pointing (Fig. 2-51).
Fig. 2-51. The switching fabric for a Batcher-banyan switch.
After exiting the Batcher switch, the cells undergo a shuffle and are then inserted into a banyan switch (see Fig. 2-52 for an example).
Fig. 2-52. An example with four cells using the Batcher-banyan switch.
In principle, the Batcher-banyan switch makes a fine ATM switch, but there are two complications: output line collision and multicasting. If two or more cells are aimed at the same output, the switch cannot handle them, so a kind of buffering has to be introduced. One way to solve this problem is by inserting a trap network between the Batcher switch and banyan switch that filters out duplicates and recirculates them for subsequent cycles, all the while maintaining the order of cells on a virtual circuit. Commercial switches also have to handle multicast.